/*partition  a[l]...a[u] into 2 parts: one less than a[l], the other more than or equal to a[l]*/
int partition(int a[], int l, int u){
	int k = a[l];
	while(l<u) {
		while(l<u && a[u]<=k) u--;
		a[l] = a[u];
		while(l<u && a[l]>k) l++;
		a[u] = a[l];
	}
	a[l] = k;
	return l;
}

/*find the k largest numbers in a[0]...a[n-1]*/
void get_klargest(int a[], int n, int k){
	int l = 0, u = n-1, m;
	while(true) {
		m = partition(a, l, u);
		if(k<m+1-l) u = m-1;
		else if(k>m+1-l) {
			k -= m+1-l;
			l = m+1;
		} else break;
	}
}

void inline swap(int &a, int &b){int temp=a;a=b;b=temp;}

/*sink a element in a min-heap*/
void min_sink(int a[], int i, int k) {
	int smaller, l = (i<<1)+1, r = l+1;
	while(l<=k){
		if(r>k || a[l]<a[r]) smaller = l;
		else smaller = r;
		if(a[i]>a[smaller]) {
			swap(a[i], a[smaller]);
			i = smaller;
		} else break;
		l = (i<<1)+1;
		r = l+1;
	}
}

/*construct a min-heap*/
void make_min_heap(int a[], int n){
	int k = ((n-2)>>1);
	while(k>-1) min_sink(a, k--, n-1);
}

/*find the k largest elements using min-heap*/
void get_klargest_heap(int a[], int n, int k){
	make_min_heap(a, k);
	for(int i=k; i<n; i++)
		if(a[i]>a[0]){
			swap(a[0], a[i]);
			min_sink(a, 0, k-1);
		}
}
